﻿function permuteUnique(nums: number[]): number[][] {
    const ans: number[][] = [];
    const perm: number[] = [];
    const vis: boolean[] = new Array(nums.length).fill(false);
    nums.sort((a, b) => a - b);
    function backtrack(idx: number) {
        if (idx === nums.length) {
            ans.push([...perm]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (vis[i] || (i > 0 && nums[i] === nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.push(nums[i]);
            vis[i] = true;
            backtrack(idx + 1);
            vis[i] = false;
            perm.pop();
        }
    }
    backtrack(0);
    return ans;
}
